package main

import (
	"math"
)

func coinChange(coins []int, amount int) int {
	dp := make([]int, amount+1)
	for i := 1; i < amount+1; i++ {
		temp := math.MaxInt32
		for _, coin := range coins {
			if i-coin < 0 {
				continue
			}
			if dp[i-coin] == -1 {
				continue
			}
			if temp > dp[i-coin]+1 {
				temp = dp[i-coin] + 1
			}
		}
		if temp == math.MaxInt32 {
			dp[i] = -1
		} else {
			dp[i] = temp
		}
	}

	return dp[amount]
}
